| class FMAP{K,T} < $STR |
|---|
| **** | Hash array based maps from key objects of type K to target objects of type T requiring writebacks. In this form void may not be a key, `key_nil' may be redefined. If K is a subtype of $IS_EQ, then `is_eq' will be used for key equality test (eg. string equality for STR), otherwise object equality is used. If K is a subtype of $HASH, then `hash' will be used for the hash value, otherwise the element `id' will be used.
_ Implementation: May be inherited with `key_eq', `key_nil', and `key_hash' redefined to get a different behavior. The tables grow by amortized doubling and so require writeback when inserting and deleting elements. We keep down the load factor to cut down on collision snowballing. The simple collision resolution allows us to support deletions, but makes the behavior quadratic with poor hash functions. Puts a sentinel at the end of the table to avoid one check while searching. |
| $STR | AREF{_} | COMPARE{_} |
| FMULTIMAP{_,_} |
| clear:SAME |
|---|
| **** | Clear out self, return the space if it has 17 or less entries otherwise return void. Self may be void. |
| copy: SAME |
|---|
| create(n:INT):SAME |
|---|
| **** | Make a table capable of dealing with `n' elements without expansion. You can simply insert into a void table to create one as well. Self may be void (and usually is). |
| create:SAME |
|---|
| delete(k:K):SAME |
|---|
| **** | A possibly new table which deletes the element with key `k' if it is contained in self. Usage: `tbl:=tbl.delete(k)'. Self may be void. |
| equals(e: $RO_MAP{K,T}): BOOL |
|---|
| **** | Returns true if all of "e"'s elements are equal to self's elts Ordering is an issue. Should be redefined to be more precise for particular descendants This will not be a useful routine until we can place FMAP under $RO_MAP |
| get(k:K):T |
|---|
| **** | If `k' is a key, return the corresponding target, otherwise return void. Self may be void. |
| get_pair(k:K):TUP{K,T} |
|---|
| **** | If `k' is a key, return the corresponding key/target pair. Otherwise return #(key_nil,void). Useful when different objects are treated as equal by `key_eq'. Self may be void. |
| has(e:T):BOOL |
|---|
| **** | True if the self has an element which is `elt_eq' to `e'. |
| has_ind(k: K): BOOL |
|---|
| insert(k:K,t:T):SAME |
|---|
| **** | A possibly new table which includes the key/target pair `k', `t'. If `k' is already present, replaces the current key and target with `k,t'. Usage: `tbl:=tbl.insert(k,t)'. Creates a new table if void(self). |
| insert_pair(p:TUP{K,T}):SAME |
|---|
| **** | Insert the key/target pair held by the tuple arg. If the key is already present, replaces it with the new key and target. `tbl:=tbl.insert(p)'. Creates a new table if void(self). |
| is_empty:BOOL |
|---|
| **** | True if the set is empty. Self may be void. |
| n_inds: INT is |
|---|
| size:INT |
|---|
| **** | Number of entries in the table. Self may be void. |
| str: STR |
|---|
| test(k:K):BOOL |
|---|
| **** | True if the key `k' is mapped by self. Self may be void. |
| elt!: T |
|---|
| filter!(once f:ROUT{T}:BOOL): T |
|---|
| filter_not!(once f:ROUT{T}:BOOL): T |
|---|
| ind!: K |
|---|
| keys!:K |
|---|
| **** | Yield the keys in self in an arbitrary order. Do not insert or delete from self while calling this. Self may be void. |
| pair!:TUP{K,T} |
|---|
| pairs!:TUP{K,T} |
|---|
| **** | Yield the input/output pairs of self in an arbitrary order. Do not insert or delete from self while calling this. Self may be void. |
| target!:T |
|---|
| targets!:T |
|---|
| **** | Yield the target objects contained in self in an arbitrary order. Do not insert or delete from self while calling this. Self may be void. |
| allocate(n:INT):SAME |
|---|
| **** | Allocate `n' locations (must be power of 2 plus 1) and initialize to `(elt_nil,void)'. |
| double_size:SAME |
|---|
| **** | A new table of twice the size of self with self's entries copied over. |
| halve_size:SAME |
|---|
| **** | A new table of half the size of self with self's entries copied over. |
| attr hsize:INT; |
|---|
| **** | Number of stored entries. |
| attr hsize:INT; |
|---|
| **** | Number of stored entries. |
| const load_ratio:INT:=4; |
|---|
| **** | Allow to get at most 1/load_ratio full. |
| not_too_many(start, finish:INT):BOOL |
|---|
| **** | A function called in an assert to check that really bad hashing isn't happening, which would probably be a performance bug. Since it is in an assert, this isn't called unless checking is on. |
| should_grow:BOOL |
|---|
| should_shrink:BOOL |
|---|